/*
		Aim: implement an hash table with open addressing scheme for the password based authentication application.
		Last edited : 27-6-2014
*/

	/* Program uses a file user.txt as its input. user.txt has username<space>password of each entry seperated by new line character*/

#include<stdio.h>
#include<string.h>			//for string manipulations
#include<math.h>
#include<stdlib.h>
#include<time.h>

struct table{
int chk;                            //check value to see if a slot is empty or not
char usid[30];			    // user id's(not more than 30 chars)
char pass[30];			    //password (not more than 30 chars)
};

int const size=23;  			// size of the hash table

int ga,gb;				//store the random value generated for universal hashing

struct table htab[22];			//hash table

void intialize()
{
	/* to intialize the hash table as an empty table with default values */
	
	int i;
	for(i=0;i<size;i++)
	{
		htab[i].chk=-1;  		//-1 represents that the slot is still empty.
		strcpy(htab[i].usid,"\0");
		strcpy(htab[i].pass,"\0");
	}
}

int getsum(char name[])
{
			/* function to calculate the ASCII sum of chars of the username and return it
			takes the username as the argument*/ 
	int i,sum=0,j;
	for(i=0,j=1;name[i]!='\0';i++,j++)
		sum+=(((int)name[i])*(10^j));
	return sum;				// contain the ASCII sum of the username
}

int div_tab(char name[])
{
	/* function to impelemt division hash function on username and return the slot */
	int k,slot;
	k=getsum(name);	
	slot=k%(size);
	return slot;
}

int mul_tab(char name[])
{
	/* function to impelemt multiplication hash function on username and return the slot */
	int k,slot;
	k=getsum(name);		
	double a=((pow(5,.5)-1)/2);
	a=a*k;
	slot=size*(fmod(a,1.0));
	return slot;	
}

int uni_getpos(char name[])
{
	/* function to get the position of the username in the hashtable using universal slot on the values earliear
	generated by the rand function earlier
		ga and gb store the earlier generated random values for universal hashing*/
	int k,pos;
	k=getsum(name);
	int p=3221;
	ga=ga*k+gb;
	pos=fmod(fmod(ga,p),size);
	return pos;
}

int uni_tab(char name[])
{
	/* function to impelemt universal hash function on username and return the slot */
	int k,slot;
	k=getsum(name);
	int a,b,p=3221;
	rand_int(&a,&b);
	a=a*k+b;
	slot=fmod(fmod(a,p),size);
	return slot;	
}

int hashfn(char name[],int ch)
{
	/* Returns the slot at which the username and password can be stored in the hash table
	   takes the username as the argument */
	int slot,k;
	k=getsum(name);
	if(ch==1)
		slot=div_tab(name);		/* division hash function*/
	else if(ch==2)
		slot=mul_tab(name);				//multiplication hash function	
	else if(ch==3)
		slot=uni_tab(name);
	while(1)
	{
		if(htab[slot].chk==-1)		// if the slot is empty
		{
			htab[slot].chk=-2;	//-2 represents that the slot is occupied now
			return slot;
		}
		else
		{
			k++;
			slot=k%(size);		// linear probing
		}   				
	}
}

int getpos(char name[],int ch)
{
	/* gets the pos of the username entered by the user in the hash table on the basis of hash function opted for.
	takes the username as the argument
	returns the slot no. if the username is found in the hash table
	and returns -1 if the username is not in the table */

	int n,slot,cmp;
	if(ch==1)
		slot=div_tab(name);
	else if(ch==2)
		slot=mul_tab(name);				//multiplication hash function	
	else if(ch==3)
		slot=uni_getpos(name);
	while(htab[slot].chk==-2)
	{
		cmp=strcmp(name,htab[slot].usid);
		if(cmp==0)
		{
			return slot;
		}
	slot++;
	}
	return -1;
}

void rand_int(int *a, int *b)
{
	/* generates 2 random variable between 3221 and 1 for universal hashing and stores them in a and b*/
	/*max chose to be 3221 because length of username is 30 and the highest ASCII value is 127. 127*30=1210
	therefor k would not be greater that 1210. smallest prime no. greater than 1210 is 1221. */ 				
	int max=3221, min=1, range, d, rmax;
	srand(time(0));
	range = max - min;
	rmax = RAND_MAX;
	d = rand();
	*a=rand()%(max-min+1)+min;
	*b=rand()%(max-min+1)+min;
	ga=*a;
	gb=*b;
}


void enter_data(int pos, char user[], char pass[])
{
	/* function to enter each entry into the specific slot of the hash table */
	strcpy(htab[pos].usid,user);
	strcpy(htab[pos].pass,pass);
}

void extract(int ch)
{
	/* Function to extract user id and password from the text file and store into the hash table in different slots*/

	char c;
	int flag=0,sum=0,i=0,slot;
	char rec1[50],rec2[30];
	FILE *fopen(),*fp;
	fp=fopen("user.txt","r");
	c = getc( fp ) ; 		
	while(c!=EOF) 		//keeps username in rec1 and pass in rec2 for each entry and then sends it be saved in hash table */
	{
		if(flag==0 && c!=' ')
		{
			rec1[i]=c;
			i++;
			c=getc(fp);
		}
		if(flag==0 && c==' ')
		{
			flag=1;
			rec1[i]='\0';	
			c=getc(fp);
			i=0;
		}
		if(flag==1 && c!='\n')
		{
			rec2[i]=c;
			i++;
			c=getc(fp);
		}
		if(flag==1 && c=='\n')
		{
			rec2[i]='\0';
			i=0;
			flag=0;
			c=getc(fp);		
			slot=hashfn(rec1,ch);		//get the slot for each entry using hash function
			enter_data(slot,rec1,rec2);	//enter the data into the hash table
		}
	}
	fclose( fp );
}

int chk(int pos, char pass[])
{
	/* function to check if the password enterd is correct or not
	takes the slot no. and the enterd password as the argument.
	function return 1 if password matches and -1 if password does not matches */

	int c;
	c=strcmp(pass,htab[pos].pass);
	if(c==0)
		return 1;		//match found
	else
		return -1;		//match not found
}

void disp_table()
{
	/* function to display the whole hash table */
	int i;
	printf("%7s %20s %20s\n\n","Slot no","Username","Password");
	for (i=0;i<size;i++)
	{
		printf("%7d %20s %20s\n",i,htab[i].usid,htab[i].pass);	
	}
}

int choose()
{
	/* function to choose which hash function is to be used by the user */
	int ch;
	printf("\n\n\tChose a hash function to hash the data into the hash table :");
	printf("\n\n1. Division Method (works well when the data is uniformly distributed over the entire range)");
	printf("\n\n2. Multiplication Method (works well with mostly all data distribution but more so with a hash table of size 2^m)");
	printf("\n\n3. Universal hashing (works quite well in all cases)");
	scanf("%d",&ch);
	return ch;
}

void main() 
{
	int pos,pc,ec=0,ch;
	char user[50],pass[30];
	intialize();
	ch=choose();
	extract(ch);
	disp_table();
	while(ec<3)			//ec counts the no. of times the user has tried to authenticate himself.
	{
	printf("\nenter the username :");
	scanf("%s",user);
	printf("enter the password  :");
	scanf("%s",pass);
	pos=getpos(user,ch);
	pc=chk(pos,pass);
	if(pc==1 && pos!=-1)
	{
		printf("\nmatch found\n");
		printf("System logged in\n");
		break;
	}
	if(pc==-1 || pos==-1)
	{	
		if(ec<2)
			printf("authentication failiure..Please Try Again!!\n");
			printf("%d try(ies) left!!",3-(ec+1));
		ec++;
	}
	}
	if(ec==3)
		printf("\nToo many tries...System Quitting...\n");
}
